package _220328;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-28-17:48
 */
public class 游园安排 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] ss = s.split("(?<!^)(?=[A-Z])");   // 按格式分割姓名

        /**  只得80分
         *   String s2 = s.replaceAll("[A-Z]", "_$0");
         *   String[] ss = s2.split("_");
         *   方法 replaceAll 可以使用正则表达式对字符串进行修改，其中：
         *
         *  [A-Z] 表示任意一个大写字母
         *  $0 表示匹配到的第一个字符（即该大写字母）
         *  _$0 表示在匹配到的大写字母前加一个下划线（作为分隔符使用）
         *  最后再使用方法 split 以下划线 ’_‘ 为分隔符分割字符串，得到结果
         *
         */

        for (String s1 : ss) {
            System.out.print(s1 + " ");
        }
        System.out.println("*******");

        int len = ss.length;
        if (len == 0) {
            return;
        }
        String[] temp = new String[len];    // 递增姓名队列
        int[] path = new int[len];  // 包含姓名i的递增姓名长度
        path[0] = 0;
        temp[0] = ss[0];
        int cur = 0;
        for (int i = 1; i < len; i++) {
            // 如果当前要插入的大于队尾 则直接插入队列，并修改path[i]
            if (ss[i].compareTo(temp[cur]) > 0) {
                cur++;
                temp[cur] = ss[i];
                path[i] = cur;
            } else if (ss[i].compareTo(temp[cur]) < 0) {    // 如果小于队尾，在队列中二分查找大于ss[i]的第一个位置插入
                int l = 0, r = cur + 1;
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (temp[mid].compareTo(ss[i]) >= 0) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                temp[l] = ss[i];
                path[i] = l;
            }
        }
        // 对结果通过path[]进行输出
        String str = "Zzzzzzzzzzzzzzzz";    // 初始设置为字典序最大的情况
        int amLen = cur;
        int[] ans = new int[cur + 1];
        for (int i = len - 1; i >= 0; i--) {
            if (cur < 0) {
                break;
            }
            if (path[i] == cur && ss[i].compareTo(str) <= 0) {
                ans[cur] = i;
                str = ss[i];
                cur--;
            }
        }
        for (int i = 0; i <= amLen; i++) {
            System.out.print(ss[ans[i]]);
        }
    }
}
